package tree.leetcode_437_medium_backtrace;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;

/**
 * leetcode417题：路径总和3
 */
public class PathSum {
    /**
     *  给定一个二叉树，它的每个结点都存放着一个整数值。
     *  找出路径和等于给定数值的路径总数。
     *  路径不需要从根节点开始，也不需要在叶子节点结束，但是路径方向必须是向下的（只能从父节点到子节点）。
     *  二叉树不超过1000个节点，且节点数值范围是 [-1000000,1000000] 的整数。
     *
     *  最简单的方法：暴力递归
     *      dfs搜索，从根结点出发，每一个节点的给定数值 = sum - root.val，
     *      如果到某一个节点时sum == root.val，就找到了一条路径，记录起来。
     *
     *      递归遍历每一个节点，找到一条路径就记录一次。
     *
     *      时间复杂度：O(N^2)：最坏情况下，一颗二叉树（节点总数为N）退化成链表 = n + (n - 1) + (n -2) + ... + 2 + 1;
     *      空间复杂度：O(N)：递归调用系统栈，栈的大小等于树的深度。
     *
     * @param root  给定一颗二叉树的根节点
     * @return      返回路径和等于给定数值的路径总数
     * @param sum   给定数值
     */
    public int pathSum(TreeNode root, int sum) {
        if(root == null){
            return 0;
        }
        /**
         * 因为从任意一个节点出发产生的结果都不一样，因此需要遍历到每一个节点。
         *      从根节点处发开始搜索的结果 + 从左孩子出发的结果 + 从右孩子出发的结果；
         */
        return dfs(root,sum) + pathSum(root.left, sum) + pathSum(root.right, sum);
    }
    public int dfs(TreeNode root, int sum){
        if(root == null){
            return 0;
        }
        int res = 0;
        if(root.val == sum){
            res = res + 1;
        }
        res += dfs(root.left, sum - root.val);
        res += dfs(root.right, sum - root.val);
        return res;
    }
}
